package com.scott.ch400.atguigu.ch100.v02;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 黄后林
 * @date 2022-08-11 08:27:19
 * @note 二分法  前提：有序
 */
public class BinarySearchV02 {

    public static void main(String[] args) {

        int[] arr={1,8,10,89,1000,1000,1000,1234,123456,1234567};
        int findVal =1000;
        List<Integer> list = binarySearch(arr, 0, arr.length - 1, findVal);
        System.out.println(list);
    }


    /**
     * 方法描述:  二分查找的递归实现
     * @author: 黄后林
     * @date: 2022/8/11 8:32
     * @param array      在哪个数组中查找
     * @param left       下标开始位置
     * @param right      下标结束位置
     * @param findVal    要查找的数
     * @return int       下标
     */
    public static List<Integer> binarySearch(int[] array, int left, int right, int findVal){

        //1 什么时候结束递归
        if(left>right){
            return new ArrayList<>();
        }

        //2 做正常的业务
        int mid =(left + right)/2;
        int midVal = array[mid];

        if(findVal > midVal){
            // 向右边继续找=向右递归
            left=mid+1;
            return binarySearch(array,left,right,findVal);
        }else if(findVal<midVal){
            // 向左边继续找=向左递归
            right=mid-1;
            return binarySearch(array,left,right,findVal);
        }else{

            // 1 不要直接返回
            List<Integer> list = new ArrayList<>();

            // 2 向左扫描
            int tempIndex = mid -1;
            while (true){
                if(tempIndex<0  || array[tempIndex] != findVal){
                    // 说明已经扫描完毕 或者 左边的第1个和我们要找的元素就不相等
                    break;
                }
                list.add(tempIndex);
                // 继续往左边扫描
                tempIndex=tempIndex-1;
            }

            // 3 加上自己
            list.add(mid);
            System.out.println("mid="+mid);

            // 4 向右扫描
            tempIndex = mid + 1;
            while (true){
                if(tempIndex>array.length-1  || array[tempIndex] != findVal){
                    // 说明已经扫描完毕 或者 右边的第1个和我们要找的元素就不相等
                    break;
                }
                list.add(tempIndex);
                // 继续往右边扫描
                tempIndex=tempIndex+1;
            }
            return list;

        }
    }


}
